package main

import (
	"container/list"
	"fmt"
)

func main() {
	nums := []int{1}
	//var nums []int
	k := 1
	fmt.Println(maxSlidingWindow(nums, k))
	fmt.Println(two(nums, k))
}

func maxSlidingWindow(nums []int, k int) []int {
	var result []int

	if k == 0 {
		return result
	}

	for i := 0; i <= len(nums)-k; i++ {
		var sli []int

		sli = nums[i : i+k]

		max := sli[0]

		for _, value := range sli {
			if value > max {
				max = value
			}
		}
		result = append(result, max)
	}

	return result
}

func two(nums []int, k int) []int {
	var result []int

	if k == 0 {
		return result
	}

	// 双端队列
	var ll *list.List

	ll = list.New()

	// 获取本次的值
	for index, value := range nums {
		if ll.Len() == 0 {
			ll.PushBack(index)
		}
		// 双向链表中有值的时候
		for {
			// 首先要将队列中比本次值小的数据弹出
			// 如果此时队列尾部的数据比该数据大则将本次数据的index放在队尾
			if ll.Len() == 0 {
				ll.PushBack(index)
				break
			}
			if value > nums[ll.Back().Value.(int)] {
				ll.Remove(ll.Back())
			} else {
				ll.PushBack(index)
				break
			}
		}
		// 判断队列头部数据是否在滑动窗口中
		// 当index到达k的值的时候才正式进入滑动窗口，当index小于k的时候属于初始化的阶段
		if index >= k-1 {
			for {
				if ll.Front().Value.(int) <= index-k {
					ll.Remove(ll.Front())
				} else {
					break
				}
			}
			result = append(result, nums[ll.Front().Value.(int)])
		}
	}
	return result
}
